package titt.util.search;

import java.util.ArrayList;

import titt.util.Bytes;

public class ByteSearch {

	private final byte[] b;

	private ByteSequence cache = null;
	private byte[] cache_id = null;

	public ByteSearch(byte[] data) {
		this.b = data;
	}

	public int indexOf(byte[] b) {
		return indexOf(b, 0);
	}

	public int indexOf(byte[] b, int fromIndex) {

		if(b != cache_id) {
			cache_id = b;
			cache = new ByteSequence(b);
		}

		byte seq = b[cache.getSequenceIndex()];

		int seq_len = cache.getSequenceLength();
		int seq_down, seq_up;
		
		byte[] suffix = cache.getSuffix(), prefix = cache.getPrefix();

		int potential = nextPotential(fromIndex, seq_len, seq);

		while(true) {

			if(potential == -1)	return -1;

			seq_down = expandSequenceDown(potential, seq, fromIndex + prefix.length);
			seq_up = expandSequenceUp(potential, seq);
			
			if(seq_up - seq_down + 1 >= seq_len && checkForSequence(seq_up + 1, suffix)
					&&
				checkForSequence(seq_down - prefix.length, prefix)) {

				int ret = -1;
				
				if(prefix.length == 0)
					ret = seq_up - seq_len + 1;

				if((suffix.length == 0 || (seq_len == (seq_up - seq_down + 1))))
					ret = seq_down - prefix.length;
				
				if(ret >= fromIndex) return ret;
			}
			
			
			potential = nextPotential(potential + seq_len,seq_len,seq);
			
		}
	}

	public byte[] subbyte(int beginindex, int endindex) {
		return Bytes.copy(b, beginindex, endindex - beginindex);
	}
	
	public byte[][] split(byte[] b) {
		ArrayList<byte[]> bytes = new ArrayList<byte[]>();

		int index = indexOf(b);

		if(index == -1) return new byte[][]{Bytes.copy(this.b, 0, this.b.length)};

		int last = 0;
				
		while(index != -1) {
			bytes.add(Bytes.copy(this.b, last, index - last));
			
			last = index + b.length;
			index = indexOf(b, index + b.length);
		}

		bytes.add(Bytes.copy(this.b, last, this.b.length - last));

		byte[][] ret = new byte[bytes.size()][];
		
		ret = bytes.toArray(ret);
		
		return ret;
	}



	private int expandSequenceDown(int from, byte seq, int min) {

		for(int h = from; h >= min; h--) {
			if(b[h] != seq) return h+1;
		}

		return min;
	}

	private int expandSequenceUp(int from, byte seq) {

		for(int h = from; h < b.length; h++) {
			if(b[h] != seq) return h-1;
		}

		return b.length-1;
	}

	private boolean checkForSequence(int from, byte[] seq) {

		if(b.length < seq.length + from) return false;
		
		for(int i = 0; i < seq.length; i++) {
			if(b[i + from] != seq[i]) return false;
		}

		return true;
		
	}
	
	private int nextPotential(int from, int seq_len, byte seq) {

		for(int i = from; i < b.length; i += seq_len) {
			if(b[i] == seq) return i;
		}

		return -1;

	}

}
